package com.gitee.swsk33.algorithms.lineartable.linkedlist.doublelinkedlist;

/**
 * 双向链表
 */
public class DoubleLinkedList<T> {

	/**
	 * 双向链表的头结点
	 */
	private DoubleNode<T> head;

	/**
	 * 构造函数初始化一个双向链表
	 */
	public DoubleLinkedList() {
		head = new DoubleNode<>();
		// 双向链表也是一种循环链表，因此开始的时候，head的前一个和后一个都指向自己
		head.setLast(head);
		head.setNext(head);
	}

	/**
	 * 在尾部插入一个元素
	 *
	 * @param data 元素值
	 */
	public void add(T data) {
		// 引用至最后一个节点
		DoubleNode<T> node = head;
		while (node.getNext() != head) {
			node = node.getNext();
		}
		// 这个时候已经到达最后一个了
		// 实例化一个节点，并让该节点的前一个指向node，后一个指向head
		DoubleNode<T> newNode = new DoubleNode<>();
		newNode.setData(data);
		newNode.setNext(head);
		newNode.setLast(node);
		// 然后再让node的下一个指向newNode
		node.setNext(newNode);
	}

	/**
	 * 插入节点
	 *
	 * @param index 插入位置，0代表第一个节点（头结点的后一个）
	 * @param data  插入节点值
	 */
	public void insert(int index, T data) throws Exception {
		// 引用至第index - 1个节点
		DoubleNode<T> node = head;
		// 可以把头结点视为第-1个节点
		for (int i = -1; i < index - 1; i++) {
			node = node.getNext();
			// 越界检测
			if (node == head) {
				throw new Exception("索引越界！");
			}
		}
		// 现在node指向第index - 1个节点
		// 实例化个新节点
		DoubleNode<T> newNode = new DoubleNode<>();
		newNode.setData(data);
		// 先把newNode的下一个指向node的下一个
		newNode.setNext(node.getNext());
		// 再把此时newNode的下一个节点的上一个指向newNode
		newNode.getNext().setLast(newNode);
		// 再把newNode的上一个指向node
		newNode.setLast(node);
		// 最后把node的下一个指向newNode
		node.setNext(newNode);
	}

	/**
	 * 删除节点
	 *
	 * @param index 待删除节点索引
	 */
	public void delete(int index) throws Exception {
		// 引用至第index - 1个节点
		DoubleNode<T> node = head;
		// 可以把头结点视为第-1个节点
		for (int i = -1; i < index - 1; i++) {
			node = node.getNext();
			// 越界检测
			if (node.getNext() == head) {
				throw new Exception("索引越界！");
			}
		}
		// 现在node指向第index - 1个节点
		// 先把node的下一个指向node的下一个的下一个
		node.setNext(node.getNext().getNext());
		// 再把此时node的下一个的上一个指向node
		node.getNext().setLast(node);
	}

	// 修改和查询是差不多的，在此不再实现

	/**
	 * 打印双向链表
	 */
	public void printList() {
		System.out.print("○");
		DoubleNode<T> node = head;
		while ((node = node.getNext()) != head) {
			System.out.print(" <-> " + node.getData());
		}
		System.out.println();
	}

}